HPAVC

home *** CD-ROM | disk | FTP | other *** search

/ HPAVC / HPAVC CD-ROM.iso / pc / CIS_GAME.ARJ / QVOXL2.THD < prev next >

Wrap

Text File | 1993-06-25 | 41.7 KB | 896 lines

______________________________ Subj: Oct Trees ______________________________ Fm: Mark Betz/Ass't SysOp 76605,2346 To: Dan Corritore 70243,1110 (X) >> I remember that discussion, although I don't recall anything about using trees in it, but then again, [ Editor's note: see VOXEL.THD, GAMERS section 11 ] That subject, which Chris Lampton, at least, knows a lot more about then I, involves using an Octree (a tree where each node has eight links). I believe it's done this way (Chris, jump in and tell me far off I am <g>): You consider your world space as a cube (or in your case a 2D rectangle) which is subdivided into eight interior cubes, each of which has a link pointer in the parent cube (in the case of the children of the root node, their parent is the world space. Within each node, a child pointer is null (the cube of space is undefined) if there is nothing in it, or has a pointer to a node if there is. That node is then subdivided according to the same rule. Each of the cubes is known as a Voxel. The advantage is that you do not store positional data for cubes (or rectangles) of empty space. As I remember this is most applicable to flight simulators, where huge portions of the world database contain nothing at all. In your case I could see using a quadtree (as above, with a four-level subdivision of a 2D rectangle). Each node would contain the rectangle extents, and a linked list of objects present in that rectangle. --Mark ........................................................................... Fm: Dan Corritore 70243,1110 To: Mark Betz/Ass't SysOp 76605,2346 (X) What you said sounds almost exactly like what Kevin Gliner suggested. In fact, it sounds a whole lot like tiles, although a tile wouldn't have a linked list, and it wouldn't be on a tree. Which is one thing I can't understand with what you said.. why not just have an array (the size of the smallest subdivision you have*(size of the world/subdivision) or something as such), with linked list pointers coming off of them? That way, you wouldn't have to traverse the tree to get to a certain section, only to traverse a linked list afterwards. What I'm using for my tree stuff isn't like that.. well, actually, I do have a few subdivisions of the world (if it's 32000*32000 pixels, the first node would be at 16000*16000, etc.. until a suitable enough division is reached.. of course, I could just use an array of tree's starting at those divisions), but I put the objects into their correct places(not on linked lists--each object has child pointers which are traversed based on compares). I hope you understood that..(and I hope I understood you correctly<g>) Thanks, _Dan ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 To: Dan Corritore 70243,1110 Well, the biggest reason is that, with an array, you'd have to check every element to see if the linked list was empty or not. With the Octree, if the space defined by the child pointer is empty, then the pointer is null. --Mark ........................................................................... Fm: Hans Peter Rushworth 100031,473 To: Dan Corritore/MOTM 70243,1110 An array would be preferred if you were interested in all points in the 3D space, even parts that are not visible. In most cases you are interested only where a surface lies in the the 3D space. You could store such a surface in a pair of 2D arrays where one array is used to indicate the altitude of a point in the surface, and the other array is used to store say a colour value for that point. The first problem with this if you have a vertical feature like a cliff, you store less surface detail than where the surface is a plain (which is usually less "interesting"). The second problem is that even if there are large areas of no interest, the storage still needs to be allocated for that area. With a voxel approach, memory is only used where detail is present, and where the surface exists. Since the voxel structure is fractal, you can add extra detail to cater for special situations that have a lot of detail, and the problem of "cliffs" is much less of a problem. For very large 3D spaces, octree (voxel) storage schemes are much more efficient than arrays, and they have the added benefit of "adaptive" resolution control, wherein you restrict the depth of your search for more distant objects. In practice you might use a hybrid approach, say have an octree of arrays. The arrays are there to provide detail that is easier to process (as you say) You might call this array a voxary <g> Peter. ........................................................................... Fm: Hans Peter Rushworth 100031,473 To: John W. Ratcliff 70253,3237 (X) No John, I have no connection with the commanche people. I'm led to believe they did not use the voxel surface representation (as I described it) because in CMO the areas with large change in altitude give rise to "tall rectangles" which is the result you would get when using two 2D arrays for colour and altittude. (Unless I remember incorrectly). Of course it's still possible they used a quadtree in place of either of the 2D arrays, but this would not be computationally efficient IMO. I have looked at CONTOUR.ZIP and I would agree that CMO probably uses a similar minmax method to mask displayed pixels in the vertical, but there is still the problem of ordering the surface altitudes, and I'm not sure what method you used for that, or whether CMO uses a similar or novel approach. I have implemented a high speed display system using a different sort of tree (a Binary Space Partitioning Tree), which was mainly used for hidden surface removal of polygon data. The BSP tree when appropriately traversed visits nodes in order of distance, irrespective of the view position. The BSP system IMO is a very efficient for static, non-intersecting databases. As for CMO, I suspect they simply calculate the vanishing points of the horizon where it meets the screen edges (which it is contrived to do always), and together with the mappings of the bottom edge screen co-ordinates, find a 4-point mapping into their altitude and colour arrays. It is then a simple matter to use incremental interpolation to sample a vertical "slice" representing colour and altitudes for each display pixel, and then paint them using the minmax hidden surface method. I have used a similar sampling scheme to map flat texture maps into arbitrarily oriented 3D polygons, and using incremental sampling, the speed can be very fast, even in C. The sampling scheme automatically deals with the replication and skipping of map pixels (if the map is visually very close, the same point is sampled more than once, if distant, pixels are "missed out"). Rotations are dealt with by transforming only the initial 4 screen corner points. All interpolated samples that are taken using these points are implicitly rotated. I could probably knock up a program to demonstrate this using a fractal plasma surface if you are interested, but you might have to wait a week or two. Peter. ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 To: Hans Peter Rushworth 100031,473 (X) >> voxarray I love it! Patent that fast <g>. I'm no expert on Octrees, but I think I have the basic concept down. What I'm wondering is what information you consider it necessary to store in each node of the tree. I'm thinking that, since the node represents a cube, you have to define the cube's extent. You then have to have a way to travel to the structures defining the objects in the space. This might be a pointer to a linked list of objects. The most puzzling question (at this moment): since the voxel space is recursively divisible down to a cube of 1 unit on a side, at what point do you stop and say "this is the cube the object or feature exists in". This is related to your mention of resolution, but I'm confused as to how to apply it. --Mark ........................................................................... Fm: Hans Peter Rushworth 100031,473 To: Mark Betz/Ass't SysOp 76605,2346 (X) >> I'm thinking that, since the node represents a cube, you have to define the cube's extent. I don't think so Mark. Imagine your 3D space was 1Km x 1Km x 1Km. The root node of the octree is a cube of those dimensions. If you subdivide this node, a child of this node is a cube 500m x 500m x 500m (ie one eigth the volume). The extent of the cube is always known by reference to its depth in the hierarchy. When "expanding" the octree, you stop when the cube dimensions would be "the same size as a pixel". If you don't subdivide this way, you have to do extra checks to make sure you don't have overlapping and inconsistent spaces. There is no limit to the amount you can subdivide the 3D space - it is fractal. >> what to store in the node. You might store a mean value (lets say colour, or material) of whatever is stored in children of the node. You can use this value when you decide not to proceed further in processing the tree. >> The most puzzling question (at this moment): since the voxel space is recursively divisible down to a cube of 1 unit on a side, at what point do you stop and say "this is the cube the object or feature exists in". This is related to your mention of resolution, but I'm confused as to how to apply it. Say your 3D space represents oil trapped beneath the surface of the earth. The resolution limit might be determined by how big a drill bit you have, or how large an volume of oil is worth drilling a hole for. It all depends on what you want to use the octree for. Peter. ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 To: Hans Peter Rushworth 100031,473 (X) I think I see, Peter. The extent of the cube is determined by the division of the parent cube. The actual location of the child space inside the parent cube is determined by it's position, i.e. top-left, middle-center, etc. I assume that the reason you put "pixel" in quotes is that the size of the pixel is not always one screen pixel. You might have a rectangular solid that is ten screen pixels on a side, and so you don't deal with it in any finer resolution. Am I getting close? There is a good discussion of Voxels in Foley, Van Dam, et al. I'll have to have a look at it tomorrow. --Mark ........................................................................... Fm: Hans Peter Rushworth 100031,473 To: Mark Betz/Ass't SysOp 76605,2346 (X) >> Am I getting close? Yes. It doesn't really matter about what you use it for, and therefore what represents what. The important thing is to realise that the organisation or "shape" of the tree actually tells you something about the space. Another interesting aspect is that you can directly get the co-ordinates of a particular voxel by knowing what route you took to get to it. Each node has upto 8 subtrees. If you number these links 0 to 7, and organise the links so that the *bits* in the *link number* indicate the 1-bit "co-ordinates" of the children in XYZ relative to this node where the X Y & Z bits are bits 0,1 and 2 respectively <thats tricky to explain!>, and as you descend the tree with a max depth "n" you store the bit number in a list, the co-ordinates (xyz) of current node is: x = 0; y = 0; z = 0; for(int i=0;i<depth;i++) { int bit = 1<<(n-i); if(list[i] & 1) x += bit; if(list[i] & 2) y += bit; if(list[i] & 4) z += bit; } Working the other way, it is easy to see a way of finding the nearest node to a point in the space given the X,Y and Z co-ordinates. Again, assuming "n" is the max depth of the tree: typedef struct vox_node { struct vox_node *link[8]; // pointers to children VOX_DATA data; // whatever... } VOX_NODE; VOX_NODE *current = root,*tmp; // unsigned so "n" can be upto 16 ;) for(unsigned mask = (1<<(n-1)) ; mask ; mask >>= 1) { probe = current->link[ ((x & mask) ? 1 : 0) + ((y & mask) ? 2 : 0) + ((z & mask) ? 4 : 0) ]; if(!probe) break; current = probe; } // Now "current" points at nearest voxel (sorry about all the shifts, this would be much easier in assembler <g>). ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 To: Hans Peter Rushworth 100031,473 (X) Hi Peter, There was an article a few months ago in C Users Journal that concerned quad-trees and quad-codes. With a quad-code is was possible to represent any two-dimensional region. I suppose your oct-tree is the same idea, and if you take it further you could encode an oct-code representing any 3-dimensional object. Have you seen the article I'm talking about? Bob __________________________ Subj: RGB to Oct Tree ___________________________ Fm: Bob Provencher/GD SL 71621,2632 To: Mark Betz/Ass't SysOp 76605,2346 (X) Hi Mark! I was thinking about the RGB to octal-code problem, and I discovered the answer, it turned out to be deceptively simple! I'll follow through my thinking to see if you agree with my conclusions. If you set up your octants so that they correspond to increases in the R, G, and B directions such that an increase in the R (or x) direction adds 2^0 to the octant number, an increase in the G adds 2^1, and B adds 2^2 then you come up with an octant map that looks something like this: 111 7 101 110 5 6 100 4 011 3 001 010 1 2 000 0 So compute the octant of an rgb value, you simply decide whether it is the second half of the line which describes the componant you're looking for. So, for example, assuming a cube 63 on a side, the first octant for the rgb value 32,32,32 is 1,1,1 or 7. However, 31, 31, 31 is in octant 0,0,0. Now what is really interesting, is that if you examine the values you get, it turns out the computing the octant is a very straightforward. At each step, to see if a value lays within the first or second half of the desired line, you need only examine the current high bit. What this means is that you can compute the oct-code down to the desired 6 octants by simply rotating the bit field that represents the RGB value! For example: RGB 63, 31, 0 RGB 0, 0, 0 RGB 63, 0, 63 (Purple) B - 000000 2^2 B - 000000 B - 111111 G - 011111 2^1 G - 000000 G - 000000 R - 111111 2^0 R - 000000 R - 111111 ------ ------ ------ Oct 133333 000000 555555 So, it's very easy to compute the oct-code, and as we discussed to find RGB values in the same region as the desired one, you only need examine those with the same leading 5 digits. This will give you the seven values to the right and up from the desired one. If you were to examine the oct-codes that had the same 4 leading digits, you would then get values, that could be to the left of the desired one. If you use the leading 4 digits, worst case would be 64 matches (highly unlikely in a 256 color pallette). At that point you'd need to do your 3-d distance computation, but, if you think about it, you only need to examine the lowest two bits! The max distance here would only be 4, so the max square root you'd need to compute would be 32! These could easily be stored in a small lookup table. What do you think? Bob ........................................................................... Fm: Dan Corritore/MOTM 70243,1110 To: Hans Peter Rushworth 100031,473 (X) I'm sorry, but I still don't understand exactly how this tree structure works, and, from what Mark said, it sounded like it wastes as much (actually, more) space as an array, since you have the tree divided up into sections, and each section either has a null pointer or a linked list.. an array would have the same stuff, in less space, and less accessing time would be required.. I guess I need a better description of the voxel tree structure.. Thanks, _Dan ........................................................................... Fm: Dan Corritore/MOTM 70243,1110 To: Mark Betz/Ass't SysOp 76605,2346 (X) Aaaaahhhhhh!!! Are we going around in circles, or what?!?<g> You said that the tree would be divided into sections, each with either a null pointer, or a linked list coming off of it, yes? That's exactly what the array would be... an array of linked lists.. if Null, there's no list, so go to your next location.. same with the tree, except it's more complicated, and takes more time.. From what I've heard from you, it sounds to me that you are wasting space both ways.. Thanks, _Dam ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 To: Bob Provencher/GD SL 71621,2632 (X) I think I'm beginning to see, Bob, but you lost me on: >> So compute the octant of an rgb value, you simply decide whether it is the >> second half of the line which describes the componant you're looking for. >> So, for example, assuming a cube 63 on a side, the first octant for the rgb >> value 32,32,32 is 1,1,1 or 7. However, 31, 31, 31 is in octant 0,0,0. and also I'm having trouble with the part about "rotating the bitfield that represents the RGB value". It appears that you're letting each set bit represent either 0, 2, or 4, and then adding them vertically. I don't get the part about rotation. Must be missing something basic. This is exciting. I definitely think you might be on to something. Is there a possibility of a "collision" in this method? In other words, can two different triplets produce the same octcode? --Mark ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 To: Mark Betz/Ass't SysOp 76605,2346 (X) Hi Mark - >> So compute the octant of an rgb value, you simply decide whether it is the >> second half of the line which describes the componant you're looking for For R,G and B lines of length 64 (0 through 63) if the value is 31, or less that bit gets a zero, otherwise it gets a one. Your just figuring out which half of the line the value lies in. >> So, for example, assuming a cube 63 on a side, the first octant for the rgb >> value 32,32,32 is 1,1,1 or 7. However, 31, 31, 31 is in octant 0,0,0. If the total cube is the cube of sides with length 64, then a "first-octant" is a subcube of the total cube. 32,32,32 lies in octant 7, or binary 111 while 31,31,31 lies in octant 0, or binary 000. >> I'm having trouble with the part about "rotating the bitfield that >> represents the RGB valueif the RGB value is 64,64,64 R = 111111 = 64 G = 111111 = 64 B = 111111 = 64 Then to get the oct-code you just rotate the bitmap 90 degrees to the right BGR 111 = 7 111 = 7 111 = 7 111 = 7 111 = 7 111 = 7 to get your oct-code. I've been thinking about it further. All we're really doing here is allowing you to do a comparison on the R, G and B values, and give them equal weight. By rotating, we're saying that we want to find values in the closest cube, not the closest color. You can define exactly how large your "closest cube" is by how many low oct-codes you ignore in an octcode. I still think there is a problem with boundary values, but I have another idea I'll tell you about tomorrow after I work it out. The problem is basically that if you're looking for the closest match to 32,32,32, and 31, 31, 31 exists in the pallette, this method wouldn't necesarily _ever_ find it as the closest, because it's sort of an equal to or greater than comparison. What we can do is also find the oct-codes for the seven combinations of RGB values that are one less the the RGB values we're looking for, this will give us those cubes that are to the left of the one we want. For example for 32, 32, 32 we should really compute a quad code for (32,32,32) - (0, 0, 0) = ( itself ) = quadcode 700000 (32,32,32) - (0, 0, 1) = (32, 32, 31) = quadcode 344444 - 0 1 0 = 32, 31, 32 = 522222 - 0 1 1 = 32, 31, 31 = 166666 - 1 0 0 = 31, 32, 32 = 611111 - 1 0 1 = 31, 32, 31 = 255555 - 1 1 0 = 31, 31, 32 = 433333 - 1 1 1 = 31, 31, 31 = 077777 The problem is, even when you drop out the last octit(?) none of the ranges fallout (become the same), but I think this is worst case. If you take a regular number at random you might find that some of the resulting codes are the same after dropping the last octal digit. This still adds up to the worst case 64 compares since now we're only ignoring the last digit, not the last two, and comparing cubes to the left as well as right. I also see a problem with this if the closest match was greater than 2 away, then you'd have to ignore the last two octal digits and search for matches. No, maybe that would still be ok? I'll play with it some more. Bob ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 To: Bob Provencher/GD SL 71621,2632 (X) Oh, I see! That bit about the rotation was just too simple a concept for me to grasp immediately <g>. So producing the octcode is very straightforward, but I still don't understand exactly what you're doing to the extent I'd need to to appreciate the comments on boundary values. I need to look at it some more, but right now I'm busy writing a set of small programs for the article. Tell you what, if you can make it work for a palette lookup, I'll work it into the article as an alternative technique, for which you will get full credit. Speaking of which, I have to send you the tree code. Basically the test programs have to be able to call two functions: void rgb_sort( char* dactable ); int rgb_match( char r, char g, char b, int t ); The first simply does any initialization work. In my case it builds the tree, and in yours it would calculate the octcodes and build the array. The second finds and returns the palette index containing the closest match to the passed color triplet. The 't' parameter is a threshold value that is specific to my type of search algorithm. It's basically the vector range on each axis that we spoke of the other night. You can ignore it. I'l send the tree package along now, so that you have the latest copy of the source code. It's very small, and hopefully very clear. --Mark ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 284350 To: Hans Peter Rushworth 100031,473 (X) Date: 23-Jan-93 17:16:43 Hi Peter - I've just finished reading OCT.DOC. I think there is some promise to the method, based on the fact that the 64^3 grid is so sparsely populated, that I wouldn't need to build the index match down to the sixth level in all cases. I can check for an entire cube having an exact index match by computing the eight corners first, then if they are not equal, computing all the values. I can readily adapt the idea of octcodes to your method, which means I won't necessarily have the overhead of a tree, or I can implement it as a tree. As you point out it may take quite a bit of memory, and I'm also wondering if building the index values for the 64^3 space (given that we won't have to compute all of these) will still take too long. It does sound promising, though, I'm going to try it out, thanks! One thing though, isn't the formula for computing the distance between to three dimensional co-ordinates the square-root of the some of the squares of the x, y and z differences, or sqr( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )? ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 284412 To: Bob Provencher/GD SL 71621,2632 (X) Date: 23-Jan-93 19:27:22 >> [distance =] sqr( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )? That is right, my brain must have flipped. >> I can check for an entire cube having an exact index match by computing the eight corners first, then if they are not equal, computing all the values. No Bob, If they are not equal, you have to bisect the cube into 8 more cubes and repeat the test for each new cube recursively. You stop doing this when all the corners are equal. The only time you actualy check all the points is when the cube you have is 2x2x2, (obviously because in that case the 8 points are all the points). Otherwise checking all the points would take a very long time. >> based on the fact that the 64^3 grid is so sparsely populated. Well, it is fully populated (every colour has an index), the storage method just identifies where the value changes from one to another, it is effectively storing the boundaries of each clump of the same index in a way that is easy to search. >> I can readily adapt the idea of octcodes to your method, which means I won't necessarily have the overhead of a tree, or I can implement it as a tree. I would do it as a tree first, just to make sure the scheme is correct. ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 284511 To: Hans Peter Rushworth 100031,473 (X) Date: 23-Jan-93 22:22:08 >> No Bob, If they are not equal, you have to bisect the cube into 8 more >> cubes and repeat the test for each new cube recursively. You stop doing >> this when all Right, I understood this but sort of typed something completely different <g>. >> Well, it is fully populated (every colour has an index), the storage >> method just identifies where the value changes from one to another, it is >> effectively storing the boundaries of each clump of the same index in a >> way that is easy to search. Right, but there will only be 256 different indexes in the tree. In some cases we may only have to search the tree to three levels (or match the octcodes by the left three). Worst case would of course be 6 levels, but that shouldn't happen unless we have some adjacant or very close colors, right? >> I would do it as a tree first, just to make sure the scheme is correct. You're right, it's easier to do it recursively first and worry about implementation details later. ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 284548 To: Bob Provencher/GD SL 71621,2632 (X) Date: 23-Jan-93 23:46:33 >> Right, but there will only be 256 different indexes in the tree. In some cases we may only have to search the tree to three levels (or match the octcodes by the left three). Worst case would of course be 6 levels, but that shouldn't happen unless we have some adjacant or very close colors, right? Right. It all depends on where the edges happen to be, you can get lucky. BTW I have no justification for the "corner" algorithm. I thought of that while I was writing that file. I've a Gut feeling it is correct, I suppose it is rather like the 4-colour (or was it 3-colour) map problem. If it fails then there is probably a faster way of searching for the nearest index. The way this would work is that you only search indexes that are (1) inside the cube being tested (2) already lying along the edges of the cube (IOW test all points along each of the edges of the cube). Initially the search set is the entire 256 colour index set. At each level of recursion, you reduce this by eliminating the cases that don't suceed the two above tests. Typically this might reduce your colour index set from 256 to 256/8, which is a substantial saving. In fact it might be a good idea to use this method in place of the 8-point test. To expand on these tests, consider the following (contrived) quadtree sub-node case: 1 1 1 1 2 2 2 2 1 * * * * * * 2 1 * *(5)* * * 2 1 * * * * * * 2 4 * * *(6)* * 3 4 * * * * * * 3 4 * * * * * * 3 4 4 4 3 3 3 3 3 You would search all the edge points finding the nearest index. In this case you find indices 1-4. The indices 5 & 6 lie inside the quad. You can now eliminate all the other indexes for subsequent recursive tests for the points marked * and this will be much quicker than checking all 256 of the indices. You should also be able to eliminate all internal indices (5 & 6) that don't ALSO appear on an edge from ALL other tests. This should speed the initial setup (tree)mendously. Peter. ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 284803 To: Hans Peter Rushworth 100031,473 (X) Date: 24-Jan-93 12:12:33 >> BTW I have no justification for the "corner" algorithm. Yeah, it seems like it has to be right. I couldn't prove it formally, but I think it must ok. >> (1) inside the cube being tested >> (2) already lying along the edges of the cube (IOW test all points along >> each of the edges of the cube). >> Initially the search set is the entire 256 colour index set. A each >> level of... I think this sort of what I was trying to do before. It failed whenever the actual closest index fell just outside the cube. It might have to be extended to one-half the width of the cube. ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 285922 To: Hans Peter Rushworth 100031,473 (X) Date: 26-Jan-93 00:07:09 I did send it to Bob. I think it was the source of his misery and lack of time spent with his fiance <g>. My implementation uses a binary space partitioning tree to partition the RGB cube at each node. The compare key rotates with each level in the tree, such that red is compared at level 0, green at level 1, blue at level 2, and so on. The tree requires 2304 bytes for a 256-color palette, and another 1500 bytes or so for the code to build and search the tree. On my 486 it will produce an accurate match in about .9 ms, depending on the depth of the search path. I'm sure it could be made faster, since the nature of palette data produces a pretty terrible looking binary tree. I'm using a staggered insertion order when building the tree to avoid hitting any gradient ranges, but I still get a very deep tree for some palettes. I'd like to know if there's a way to balance a BSP tree. I suspect there isn't, since the relative position of nodes in the tree is part of the information contained. Have any ideas on this? Btw, what's your schedule this weekend? I'd like to give you a call, and need a good time. Could you PRI your number to me in case I can't find it? --Mark ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 286098 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 26-Jan-93 11:20:56 >> I'd like to know if there's a way to balance a BSP tree. I don't know if this helps in thinking about it, but three levels of BSP tree can be equivalent to a single octree node. In that case I would imagine the max depth of your tree is 18 (6x3), and that sounds reasonable to me. I'm quite amazed that your tree uses only 2304 bytes, which is much less than I would have guessed, but I suppose that can change depending on the colours that are actually in the palette. >> the relative position of nodes in the tree is part of the information contained. One way to find out is to alter the ordering scheme (instead of R, G then B) try B, G then R. To balance the tree try to pick the partition (R G or B) that splits the tree with even "weight" on either side at any given level. This heuristic won't always give the optimum balance, but is perhaps a good place to start. Usually you will want to ensure that for three levels of the tree you have selected an R G & B transition at least once. But Imagine also a palette that has only Red and Green and no blue colours. ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 286162 To: Hans Peter Rushworth 100031,473 Date: 26-Jan-93 13:59:07 Hi, Peter. Interesting. Btw, the size of the tree doesn't change depending on the colors in the palette. I don't look for duplicates: each triplet gets a node. Each node consists of a triplet, two child pointers, and the index of the original palette entry on which the node is based. Since the tree is actually built in an array, the child pointers are 2-byte indices, and not 4 byte pointers, saving 2 words per node. I think your estimate of the max depth is pretty close. Part of the constraint of searching this kind of tree, is that you have to search both subtrees anytime the current node falls within a "window" on either side of the compare key. So for certain colors I end up searching 30-40 nodes. A lot better than searching the whole palette, but there must be room for improvement. --Mark ________________________ Subj: VGA Transparency code ________________________ Fm: VOR Technologies Inc 71333,134 # 312076 To: ALL Date: 11-Mar-93 10:23:25 All, Does anyone know of some existing code or have a good algorthym for doing blends/mixes/transparencies etc with the VGA Palette. There are a couple of things though, given that i am using a static 256 color palette (256 colors were chosen and cant be changed for this program). Does anyone know of an algorythm for selecting a value for a color that shows through another color (i.E. i have a red rectanlg i place a blue one on top that i deem to be 50% trasnparent i should then be able to choose something in the purple area). I know various graphics program do it, but am not sure of an algorythm or existing code that might be available. Thanks, Chris Eisnaugle Vor Technologies Inc. ........................................................................... Fm: Jaimi McEntire 71700,1202 # 312143 To: VOR Technologies Inc 71333,134 (X) Date: 11-Mar-93 12:49:40 Chris, You could do it the "Cheesy" way... ie: Multiply the transparent color register (R,G,and B seperately) byt the transparency amount, multiply the color which you're plotting on by the remainder, add the R from source and dest, G from source and dst, and B from source and dest. then divide the results by 100, and that should give you the optimum RGB. Then just search through your palette to find the closest match. pixel = GetPixel(x,y) pixel.red *= transparency_perc; pixel.green *= transparency_perc; pixel.blue *= transparency_perc; destpixel = GetPixel(destx,desty); destpixel.red *= (100-transparency_perc); destpixel.green *= (100-transparency_perc); destpixel.blue *= (100-transparency_perc); optimum.red = (pixel.red + destpixel.red)/100; optimum.green = (pixel.green + destpixel.green)/100; optimum.blue = (pixel.blue + destpixel.blue)/100; // now find optimum color in palette. // and set dest pixel to closest to optimum Good luck! P.S. this wont compile obviously. It's just an algorithm and a slow one. you could get much better performance if you used shifts, instead of divides, but then you would need to limit the transparency levels. Jaimi McEntire ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 312351 To: VOR Technologies Inc 71333,134 (X) Date: 11-Mar-93 20:36:07 Hi, Chris. If you want to put Jaimi's method to work, I have some code which will select the best match for a given RGB from a palette. It builds a binary search tree of color values, and takes about .10 ms to do a lookup on my 486-33. The code and data is about 5K. --Mark ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 312780 To: VOR Technologies Inc 71333,134 (X) Date: 12-Mar-93 21:26:44 I'll send it along tonight, Chris. The code is public domain, but I'd appreciate it if you didn't distribute it until after July, since it is part of an article that I have submitted to a magazine. --Mark ___________________________ Subj: Mark's article ___________________________ Fm: Patrick Reilly 71333,2764 # 376998 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 15-Jun-93 19:49:12 Mark, Thanks - I look forward to reading it (haven't gotten the last DDJ yet)... I was thinking about bitmap transforms; do you know if its possible, probable, desirable, or already done <g> to take a square bitmap whose elements are made up of a RGB triple and have a transform matrix that, if you multiply your bitmap times it, will shade it for distance and do a "nice" rotation/translation of it? IOW if you start out with, say, a 4x4 matrix that's a bitmap that represents a (tiny) wall in RGB triplets when viewed head-on at a distance of 0 - can a single matrix of RGBs be created that will translate, rotate, and shade for distance the bitmap (with a specific RGB quantity - say, <0,0,0> set to be 'transparent') so that if you now displayed the bitmap, it would look like a 3D rendered texture of a wall that's 3 units away and rotated about the vertical axis 60 degrees (with depth shading)? I was going to start playing with the idea (this would allow having all the bitmaps for the walls, floors and ceilings loaded into memory, a list of about 40 or so of these transform matrices, and drawing a 'world' would only require doing the matrix multiply for each panel with the appropriate transform, do another transform for the new bitmap's starting <x,y> location on the screen, and displaying) but if this is 'old hat' <g> or has been tried and found lacking, or is plain impossible, then I won't waste my time. I read Abrash's articles for X-Sharp, but for something like a fixed view of panels which, in real-world coords, form a lattice, it seems that's not a very good approach... -Pat- ........................................................................... Fm: Patrick Reilly 71333,2764 # 377238 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 16-Jun-93 00:17:25 Mark, I figured to use a lookup table to map the RGB triplet to a palette entry; this would eliminate the problem of having to have the palette laid out so that, for example, dark colors are near 0, light colors near 255, etc, but would still allow having a triplet so that the transform matrix would make 'sense'. Also, multiplying the bitmap by a scalar would make sense too: IE using a scalar of <0.75,0.75,0.75> would darken the whole bitmap evenly to 3/4 intensity. With a lookup table, I would think the conversion (from 1-byte element matrix to RGB element matrix) would be quick enough. Of course, each conversion would require a filter to 'round' the RGB value to the 'nearest' mapping element. So you haven't heard of anyone trying this? I'll have to play a bit <g>; what I would like to end up with is: 1) convert the NxN bitmap to an NxN RGB matrix; 2) multiply the matrix by the appropriate transform matrix (IE if this panel is the 'floor' at cell <-3,+4> from current POV, use transformMatrix[18]); 3) use a filter on the transformed matrix so that the RGB elements can map to palette entries; 4) convert the matrix back into a bitmap; 5) look up the <x,y> pair for a floor at <-3,+4> from the POV and paint the bitmap at <x,y>. If it *can* be done (ie one matrix will do the complete conversion), then a nice, slow, floating-point program can generate all the transforms and lookup tables for the <x,y> coords. Once these are calculated, they can just be hardcoded into the program. I'll let you know if I can come up with anything. -Pat- ........................................................................... Fm: Patrick Reilly 71333,2764 # 377289 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 16-Jun-93 04:27:26 Mark, Oh well... its a no-show on a simple transform. A simple example shows why: consider having a 4x4 bitmap (elements A(ij)), and wanting it to be transformed onto the 'floor' panel immediately in front of the view plane; what I'd want when the transform is complete would be for A(41) to have the colors 0.65*(0.5*A(41) + 0.5*A(31)). To get such a product, the bitmap would have to multiply on the right the transform matrix; but A(32) wants to be 0.03*A(31) + 0.5*A(32) + ..., which means that the bitmap has to multiply on the *left* the transform matrix... I'll play some more; maybe its possible to use 2 matrices; one that multiplies on the left and transforms/alias' vertical pixels, and one that multiplies on the right and transforms/alias' horizontal pixels, then sum the two resultant RGB bitmaps... The bummer is that now I'd have to store *twice* as many matrices... ...........................................................................